//234. 回文链表
// 方法一：
var isPalindrome = function(head) {
    if(!head || !head.next){
        return head;
    }
    let stack = [];
    let cur = head;
    while(cur){
        stack.push(cur.val);
        cur = cur.next;
    }
    cur = head;
    while(cur){
        if(cur.val !== stack.pop()){
            return false;
        }
        cur = cur.next;
    }
    return true;
};
//方法二：时间复杂度为O(n),空间复杂度为O(1);
var isPalindrome = function(head) {
    if (!head || !head.next) {
        return true;
    }
    //获取中点位置
    let slow = head, fast = head;
    while (fast.next && fast.next.next) {
        slow = slow.next;
        fast = fast.next.next;
    }
    // 将剩下的位置逆序
    fast = slow.next;
    slow.next = null;
    let index;
    while (fast != null) {
        index = fast.next;
        fast.next = slow;
        slow = fast;
        fast = index;
    }
    //进行从两端到中间比较
    index = slow;
    fast = slow;//链表末尾的位置1 2 3 4(null) 3 2 1
    slow = head;
    let res = false;
    while (slow && fast) {
        if (slow.val != fast.val) {
            return res;
        }
        slow = slow.next;
        fast = fast.next;
    }
    // 下面为已经判断为回文串，再将中点后面的链表逆序
    fast = index;
    slow = null;
    while (fast) {
        index = fast.next;
        fast.next = slow;
        slow = fast;
        fast = index;
    }
    res = !res;
    return res;
}